/*-------------------------------------------------------------------------
 *
 * execGrouping.c
 *	  执行器工具例程用于分组、哈希和聚合
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *	  src/backend/executor/execGrouping.c
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include "access/parallel.h"
#include "common/hashfn.h"
#include "executor/executor.h"
#include "miscadmin.h"
#include "utils/lsyscache.h"
#include "utils/memutils.h"

static int	fc_TupleHashTableMatch(struct tuplehash_hash *fc_tb, const MinimalTuple fc_tuple1, const MinimalTuple fc_tuple2);
static inline uint32 fc_TupleHashTableHash_internal(struct tuplehash_hash *fc_tb,
												 const MinimalTuple fc_tuple);
static inline TupleHashEntry fc_LookupTupleHashEntry_internal(TupleHashTable hashtable,
														   TupleTableSlot *fc_slot,
														   bool *fc_isnew, uint32 fc_hash);

/*
 * 定义元组哈希表代码生成的参数。该接口也在 execnodes.h 中声明
 * （用于生成外部可见的类型）。
 */
#define SH_PREFIX tuplehash
#define SH_ELEMENT_TYPE TupleHashEntryData
#define SH_KEY_TYPE MinimalTuple
#define SH_KEY firstTuple
#define SH_HASH_KEY(tb, key) fc_TupleHashTableHash_internal(tb, key)
#define SH_EQUAL(tb, a, b) fc_TupleHashTableMatch(tb, a, b) == 0
#define SH_SCOPE extern
#define SH_STORE_HASH
#define SH_GET_HASH(tb, a) a->hash
#define SH_DEFINE
#include "lib/simplehash.h"


/*****************************************************************************
 *		用于将元组分组在一起的实用程序例程
 *****************************************************************************/

/*
 * execTuplesMatchPrepare
 *		构建可通过 ExecQual() 评估的表达式，返回
 *		一个 ExprContext 的内部/外部元组是否不相同
 */
ExprState * execTuplesMatchPrepare(TupleDesc fc_desc,
					   int fc_numCols,
					   const AttrNumber *fc_keyColIdx,
					   const Oid *fc_eqOperators,
					   const Oid *fc_collations,
					   PlanState *fc_parent)
{
	Oid		   *fc_eqFunctions = (Oid *) palloc(fc_numCols * sizeof(Oid));
	int			fc_i;
	ExprState  *fc_expr;

	if (fc_numCols == 0)
		return NULL;

	/* 查找相等函数 */
	for (fc_i = 0; fc_i < fc_numCols; fc_i++)
		fc_eqFunctions[fc_i] = get_opcode(fc_eqOperators[fc_i]);

	/* 构建实际表达式 */
	fc_expr = ExecBuildGroupingEqual(fc_desc, fc_desc, NULL, NULL,
								  fc_numCols, fc_keyColIdx, fc_eqFunctions, fc_collations,
								  fc_parent);

	return fc_expr;
}

/*
 * execTuplesHashPrepare
 *		查找 TupleHashTable 所需的相等和哈希函数。
 *
 * 这与 execTuplesMatchPrepare 类似，但我们还需要找到与
 * 相等操作符相关联的哈希函数。*eqFunctions 和 *hashFunctions
 * 接收分配的结果数组。
 *
 * 注意：我们期望给定的操作符不是跨类型比较。
 */
void execTuplesHashPrepare(int fc_numCols,
					  const Oid *fc_eqOperators,
					  Oid **fc_eqFuncOids,
					  FmgrInfo **fc_hashFunctions)
{
	int			fc_i;

	*fc_eqFuncOids = (Oid *) palloc(fc_numCols * sizeof(Oid));
	*fc_hashFunctions = (FmgrInfo *) palloc(fc_numCols * sizeof(FmgrInfo));

	for (fc_i = 0; fc_i < fc_numCols; fc_i++)
	{
		Oid			fc_eq_opr = fc_eqOperators[fc_i];
		Oid			fc_eq_function;
		Oid			fc_left_hash_function;
		Oid			fc_right_hash_function;

		fc_eq_function = get_opcode(fc_eq_opr);
		if (!get_op_hash_functions(fc_eq_opr,
								   &fc_left_hash_function, &fc_right_hash_function))
			elog(ERROR, "could not find hash function for hash operator %u",
				 fc_eq_opr);
		/* 我们在这里不支持跨类型情况 */
		Assert(fc_left_hash_function == fc_right_hash_function);
		(*fc_eqFuncOids)[fc_i] = fc_eq_function;
		fmgr_info(fc_right_hash_function, &(*fc_hashFunctions)[fc_i]);
	}
}


/*****************************************************************************
 *		用于全内存哈希表的实用程序例程
 *
 * 这些例程构建哈希表以将元组分组在一起（例如，用于哈希聚合）。
 * 对于每一组不相同的元组集合存在一个条目。
 *****************************************************************************/

/*
 * 构建一个空的 TupleHashTable
 *
 *	numCols, keyColIdx：标识用于查找键的元组字段
 *	eqfunctions：要使用的相等比较函数
 *	hashfunctions：要使用的数据类型特定哈希函数
 *	nbuckets：哈希表大小的初步估计
 *	additionalsize：存储在 ->additional 中的数据大小
 *	metacxt：用于长寿命分配的内存上下文，但不是每条目的数据
 *	tablecxt：存储表条目的内存上下文
 *	tempcxt：用于评估哈希和比较函数的短寿命上下文
 *
 * 函数数组可以使用 execTuplesHashPrepare() 创建。注意它们
 * 不是跨类型的函数，但期望在两侧看到表数据类型。
 *
 * 请注意，keyColIdx、eqfunctions 和 hashfunctions 必须分配在
 * 与哈希表同样长寿的存储中。
 */
TupleHashTable
BuildTupleHashTableExt(PlanState *fc_parent,
					   TupleDesc fc_inputDesc,
					   int fc_numCols, AttrNumber *fc_keyColIdx,
					   const Oid *fc_eqfuncoids,
					   FmgrInfo *fc_hashfunctions,
					   Oid *fc_collations,
					   long fc_nbuckets, Size fc_additionalsize,
					   MemoryContext fc_metacxt,
					   MemoryContext fc_tablecxt,
					   MemoryContext fc_tempcxt,
					   bool fc_use_variable_hash_iv)
{
	TupleHashTable hashtable;
	Size		fc_entrysize = sizeof(TupleHashEntryData) + fc_additionalsize;
	Size		fc_hash_mem_limit;
	MemoryContext fc_oldcontext;
	bool		fc_allow_jit;

	Assert(fc_nbuckets > 0);

	/* 将初始表大小请求限制为不超过 hash_mem */
	fc_hash_mem_limit = get_hash_memory_limit() / fc_entrysize;
	if (fc_nbuckets > fc_hash_mem_limit)
		fc_nbuckets = fc_hash_mem_limit;

	fc_oldcontext = MemoryContextSwitchTo(fc_metacxt);

	hashtable = (TupleHashTable) palloc(sizeof(TupleHashTableData));

	hashtable->numCols = fc_numCols;
	hashtable->keyColIdx = fc_keyColIdx;
	hashtable->tab_hash_funcs = fc_hashfunctions;
	hashtable->tab_collations = fc_collations;
	hashtable->tablecxt = fc_tablecxt;
	hashtable->tempcxt = fc_tempcxt;
	hashtable->entrysize = fc_entrysize;
	hashtable->tableslot = NULL;	/* 在第一次查找时将被使用 */
	hashtable->inputslot = NULL;
	hashtable->in_hash_funcs = NULL;
	hashtable->cur_eq_func = NULL;

	/*
	 * 如果使用并行处理，即使领导后端正在自身执行扫描，
	 * 我们也不想在所有工作者中以完全相同的方式创建哈希表。
	 * 由于哈希表是在键空间顺序中迭代的，所有进程以相同方式
	 * 执行将导致在初始表大小估计不足时出现“失衡”哈希表。
	 */
	if (fc_use_variable_hash_iv)
		hashtable->hash_iv = murmurhash32(ParallelWorkerNumber);
	else
		hashtable->hash_iv = 0;

	hashtable->hashtab = tuplehash_create(fc_metacxt, fc_nbuckets, hashtable);

	/*
	 * 我们只是为了安全起见复制输入元组描述符——我们假设所有
	 * 输入元组将具有相等的描述符。
	 */
	hashtable->tableslot = MakeSingleTupleTableSlot(CreateTupleDescCopy(fc_inputDesc),
													&TTSOpsMinimalTuple);

	/*
	 * 如果使用的是旧的重置接口（即 BuildTupleHashTable，
	 * 而不是 BuildTupleHashTableExt），允许 JIT 将导致生成的
	 * 函数 a) 比查询生命周期长 b) 每次重新设置表时会重新生成。
	 * 因此，在这种情况下，通过不提供父节点来防止使用 JIT
	 * （这会防止访问 EState 中的 JitContext）。
	 */
	fc_allow_jit = fc_metacxt != fc_tablecxt;

	/* 为所有列构建比较器 */
	hashtable->tab_eq_func = ExecBuildGroupingEqual(fc_inputDesc, fc_inputDesc,
													NULL, &TTSOpsMinimalTuple,
													fc_numCols,
													fc_keyColIdx, fc_eqfuncoids, fc_collations,
													fc_allow_jit ? fc_parent : NULL);

	
/*
	 * 虽然不太美观，但是不关闭这个上下文是没关系的，而是依靠包含的内存上下文被重置，因为
	 * ExecBuildGroupingEqual() 只构建一个非常简单的表达式调用
	 * 函数（即没有使用 RegisterExprContextCallback() 的内容）。
	 */
	hashtable->exprcontext = CreateStandaloneExprContext();

	MemoryContextSwitchTo(fc_oldcontext);

	return hashtable;
}

/*
 * BuildTupleHashTable 是一个兼容性包装器，用于
 * BuildTupleHashTableExt()，它在 tablecxt 中分配哈希表的元数据。
 * 请注意，以这种方式创建的哈希表不能通过 
 * ResetTupleHashTable() 无泄漏地重置。
 */
TupleHashTable
BuildTupleHashTable(PlanState *fc_parent,
					TupleDesc fc_inputDesc,
					int fc_numCols, AttrNumber *fc_keyColIdx,
					const Oid *fc_eqfuncoids,
					FmgrInfo *fc_hashfunctions,
					Oid *fc_collations,
					long fc_nbuckets, Size fc_additionalsize,
					MemoryContext fc_tablecxt,
					MemoryContext fc_tempcxt,
					bool fc_use_variable_hash_iv)
{
	return BuildTupleHashTableExt(fc_parent,
								  fc_inputDesc,
								  fc_numCols, fc_keyColIdx,
								  fc_eqfuncoids,
								  fc_hashfunctions,
								  fc_collations,
								  fc_nbuckets, fc_additionalsize,
								  fc_tablecxt,
								  fc_tablecxt,
								  fc_tempcxt,
								  fc_use_variable_hash_iv);
}

/*
 * 重置哈希表的内容为空，同时保留所有非内容状态。
 * 注意，传递给 BuildTupleHashTableExt() 的 tablecxt 也应该
 * 被重置，否则会出现泄漏。
 */
void ResetTupleHashTable(TupleHashTable hashtable)
{
	tuplehash_reset(hashtable->hashtab);
}

/*
 * 查找或创建包含给定元组的元组组的哈希表条目。
 * 元组必须与哈希表条目类型相同。
 *
 * 如果 isnew 为 NULL，我们不创建新条目；如果没有找到匹配项，我们返回 NULL。
 *
 * 如果 hash 不为 NULL，我们将其设置为计算出的哈希值。这允许
 * 调用者访问哈希值，即使没有返回条目。
 *
 * 如果 isnew 不为 NULL，则如果没有现有条目匹配，将创建一个新条目。
 * 返回时，如果条目是新创建的，则 *isnew 为真，
 * 如果已存在，则为假。新条目的 ->additional_data 已被置零。
 */
TupleHashEntry LookupTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *fc_slot,
					 bool *fc_isnew, uint32 *fc_hash)
{
	TupleHashEntry fc_entry;
	MemoryContext fc_oldContext;
	uint32		fc_local_hash;

	/* 需要在短生命周期上下文中运行哈希函数 */
	fc_oldContext = MemoryContextSwitchTo(hashtable->tempcxt);

	/* 设置哈希和匹配函数所需的数据 */
	hashtable->inputslot = fc_slot;
	hashtable->in_hash_funcs = hashtable->tab_hash_funcs;
	hashtable->cur_eq_func = hashtable->tab_eq_func;

	fc_local_hash = fc_TupleHashTableHash_internal(hashtable->hashtab, NULL);
	fc_entry = fc_LookupTupleHashEntry_internal(hashtable, fc_slot, fc_isnew, fc_local_hash);

	if (fc_hash != NULL)
		*fc_hash = fc_local_hash;

	Assert(fc_entry == NULL || fc_entry->hash == fc_local_hash);

	MemoryContextSwitchTo(fc_oldContext);

	return fc_entry;
}

/*
 * 计算元组的哈希值
 */
uint32 TupleHashTableHash(TupleHashTable hashtable, TupleTableSlot *fc_slot)
{
	MemoryContext fc_oldContext;
	uint32		fc_hash;

	hashtable->inputslot = fc_slot;
	hashtable->in_hash_funcs = hashtable->tab_hash_funcs;

	/* 需要在短生命周期上下文中运行哈希函数 */
	fc_oldContext = MemoryContextSwitchTo(hashtable->tempcxt);

	fc_hash = fc_TupleHashTableHash_internal(hashtable->hashtab, NULL);

	MemoryContextSwitchTo(fc_oldContext);

	return fc_hash;
}

/*
 * LookupTupleHashEntry 的一种变体，适用于已经计算
 * 哈希值的调用者。
 */
TupleHashEntry LookupTupleHashEntryHash(TupleHashTable hashtable, TupleTableSlot *fc_slot,
						 bool *fc_isnew, uint32 fc_hash)
{
	TupleHashEntry fc_entry;
	MemoryContext fc_oldContext;

	/* 需要在短生命周期上下文中运行哈希函数 */
	fc_oldContext = MemoryContextSwitchTo(hashtable->tempcxt);

	/* 设置哈希和匹配函数所需的数据 */
	hashtable->inputslot = fc_slot;
	hashtable->in_hash_funcs = hashtable->tab_hash_funcs;
	hashtable->cur_eq_func = hashtable->tab_eq_func;

	fc_entry = fc_LookupTupleHashEntry_internal(hashtable, fc_slot, fc_isnew, fc_hash);
	Assert(fc_entry == NULL || fc_entry->hash == fc_hash);

	MemoryContextSwitchTo(fc_oldContext);

	return fc_entry;
}

/*
 * 搜索与给定元组匹配的哈希表条目。如果没有匹配，不会创建条目。
 * 这与 LookupTupleHashEntry 的不创建情况类似，但它支持
 * 跨类型比较，其中给定的元组与表条目不是同一种类型。调用者
 * 必须提供用于输入元组的哈希函数以及相等函数，因为这些函数
 * 可能与表的内部函数不同。
 */
TupleHashEntry FindTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *fc_slot,
				   ExprState *fc_eqcomp,
				   FmgrInfo *fc_hashfunctions)
{
	TupleHashEntry fc_entry;
	MemoryContext fc_oldContext;
	MinimalTuple fc_key;

	/* 需要在短生命周期上下文中运行哈希函数 */
	fc_oldContext = MemoryContextSwitchTo(hashtable->tempcxt);

	/* 设置哈希和匹配函数所需的数据 */
	hashtable->inputslot = fc_slot;
	hashtable->in_hash_funcs = fc_hashfunctions;
	hashtable->cur_eq_func = fc_eqcomp;

	/* 搜索哈希表 */
	fc_key = NULL;					/* 引用输入槽的标志 */
	fc_entry = tuplehash_lookup(hashtable->hashtab, fc_key);
	MemoryContextSwitchTo(fc_oldContext);

	return fc_entry;
}

/*
 * 如果元组为 NULL，则使用输入槽。该约定避免了在实际需要复制
 * 到表中时，需物化虚拟输入元组。
 *
 * 此外，调用者必须选择适当的内存上下文来运行哈希函数。
 * （dynahash.c 不会更改 CurrentMemoryContext。）
 */
static uint32 fc_TupleHashTableHash_internal(struct tuplehash_hash *fc_tb,
							const MinimalTuple fc_tuple)
{
	TupleHashTable hashtable = (TupleHashTable) fc_tb->private_data;
	int			fc_numCols = hashtable->numCols;
	AttrNumber *fc_keyColIdx = hashtable->keyColIdx;
	uint32		fc_hashkey = hashtable->hash_iv;
	TupleTableSlot *fc_slot;
	FmgrInfo   *fc_hashfunctions;
	int			fc_i;

	if (fc_tuple == NULL)
	{
		/* 处理当前输入元组以用于表 */
		fc_slot = hashtable->inputslot;
		fc_hashfunctions = hashtable->in_hash_funcs;
	}
	else
	{
		/*
		 * 处理已存储在表中的元组。
		 *
		 * （由于 simplehash.h 的使用方式，该情况实际上从未发生，
		 * 因为哈希值存储在条目中）
		 */
		fc_slot = hashtable->tableslot;
		ExecStoreMinimalTuple(fc_tuple, fc_slot, false);
		fc_hashfunctions = hashtable->tab_hash_funcs;
	}

	for (fc_i = 0; fc_i < fc_numCols; fc_i++)
	{
		AttrNumber	fc_att = fc_keyColIdx[fc_i];
		Datum		fc_attr;
		bool		fc_isNull;

		/* 通过旋转组合连续的哈希键 */
		fc_hashkey = pg_rotate_left32(fc_hashkey, 1);

		fc_attr = slot_getattr(fc_slot, fc_att, &fc_isNull);

		if (!fc_isNull)			/* 将 null 视为哈希键 0 */
		{
			uint32		fc_hkey;

			fc_hkey = DatumGetUInt32(FunctionCall1Coll(&fc_hashfunctions[fc_i],
													hashtable->tab_collations[fc_i],
													fc_attr));
			fc_hashkey ^= fc_hkey;
		}
	}

	/*
	 * 上述哈希的组合方式，使得彼此之间与 IV 的组合，并未
	 * 带来良好的位扰动。由于 IV 的目标是实现这一点，
	 * 因此对组合的哈希进行一轮哈希处理，导致近乎完美的扰动。
	 */
	return murmurhash32(fc_hashkey);
}

/*
 * 执行 LookupTupleHashEntry 和 LookupTupleHashEntryHash 的工作。
 * 有用的是，我们可以避免为 LookupTupleHashEntry 多次切换内存上下文。
 *
 * 注意：此函数可能会或可能不会更改内存上下文。期望调用者
 * 将其更改回来。
 */
static inline TupleHashEntry
fc_LookupTupleHashEntry_internal(TupleHashTable hashtable, TupleTableSlot *fc_slot,
							  bool *fc_isnew, uint32 fc_hash)
{
	TupleHashEntryData *fc_entry;
	bool		fc_found;
	MinimalTuple fc_key;

	fc_key = NULL;					/* 引用输入槽的标志 */

	if (fc_isnew)
	{
		fc_entry = tuplehash_insert_hash(hashtable->hashtab, fc_key, fc_hash, &fc_found);

		if (fc_found)
		{
			/* 找到现有条目 */
			*fc_isnew = false;
		}
		else
		{
			/* 创建新条目 */
			*fc_isnew = true;
			/* 将调用者数据归零 */
			fc_entry->additional = NULL;
			MemoryContextSwitchTo(hashtable->tablecxt);
			/* 将第一个元组复制到表上下文中 */
			fc_entry->firstTuple = ExecCopySlotMinimalTuple(fc_slot);
		}
	}
	else
	{
		fc_entry = tuplehash_lookup_hash(hashtable->hashtab, fc_key, fc_hash);
	}

	return fc_entry;
}

/*
 * 查看两个元组（假定具有相同的哈希值）是否匹配
 */
static int fc_TupleHashTableMatch(struct tuplehash_hash *fc_tb, const MinimalTuple fc_tuple1, const MinimalTuple fc_tuple2)
{
	TupleTableSlot *fc_slot1;
	TupleTableSlot *fc_slot2;
	TupleHashTable hashtable = (TupleHashTable) fc_tb->private_data;
	ExprContext *fc_econtext = hashtable->exprcontext;

	/*
	 * 我们假设 simplehash.h 仅在第一个参数是实际表条目
	 * 以及第二个参数是 LookupTupleHashEntry 的虚拟 TupleHashEntryData 
	 * 的情况下调用我们。也可以支持反向情况，但当前
	 * 不需要。
	 */
	Assert(fc_tuple1 != NULL);
	fc_slot1 = hashtable->tableslot;
	ExecStoreMinimalTuple(fc_tuple1, fc_slot1, false);
	Assert(fc_tuple2 == NULL);
	fc_slot2 = hashtable->inputslot;

	/* 对于跨类型比较，输入槽必须在前 */
	fc_econtext->ecxt_innertuple = fc_slot2;
	fc_econtext->ecxt_outertuple = fc_slot1;
	return !ExecQualAndReset(hashtable->cur_eq_func, fc_econtext);
}
